// 9.3 doesn't work if duplicate entries
/*
 * a sorted array rorated unknown number of times, give an O(logn) algorithm find a element
 */
class SearchRotatedArray{
	public SearchRotatedArray(){
	
	}
	
	public static int rotated_binary_search(int[] a, int key){
		int left = 0;
		int right = a.length - 1;
		if(a == null || a.length = 0) return -1;
		if (a.length = 1 && a[0] == key ) return 0;
		while (left <= right){
			int middle = left + (right - left)/2;
			if(a[middle] == key) return middle;
			if (a[left]<=a[middle]){ // left part is sorted
				if(a[left]<=key && key <a[middle]) right = middle -1;
				else
				left = middle + 1;				
		} else { // right part is sorted
			if(a[middle]<=key && key < a[right] )
				left = middle + 1;	
			else
				right = middle -1;
			}
		}
		return -1;
	}
	
	public static int findPivot(int[] a){
		int left = 0;
		int right = a.length - 1;
		while(a[left] > a[right]){
			int middle = (left + right)/2;
			if (a[middle]>a[right]) 
				left = middle + 1;
			else 
				right = middle;
		}
		return right;
	}

/*
 * Solution from BOOK
 */	
	public static int search(int[] a, int begin, int end, int elem){
		if(begin == end) {
			if(a[begin] == elem){
				return begin;
			} else {
				return -1;
			}
		}
		
		if(begin > a.length - 1 || end > a.length - 1){
			return -1;
		}
		
		while( begin <= end ){
			int med = (begin + end) /2;	
			if (elem == a[med]){
				return med;
			} else if (a[begin] <= a[med]){ //ordered
				if (elem <= a[med] && elem >= a[begin])
					end = med - 1;
				else
					begin = med + 1;
			// pivot begin > med	
			} else if(elem > a[med] && elem <= a[end])
				begin = med + 1;
			else
				end = med - 1;
				
		}
		return -1;
	}
	
	public static int search(int[] a, int elem){
		return search(a, 0, a.length-1, elem);
	}
/** End of Solution **/	
	
	// Find the pivot
	public static int findPivot(int[] a){
		if(a == null){
			throw new IllegalArgumentException("array parameter is NULL!");
		}
		if(a[0]<=a[a.length - 1]) return 0;
		int left = 0;
		int right = a.length -1;
		while(left != right){
			int med = (left+right)/2;
			if(a[left] > a[med]){ // go left
				if(a[med-1]>a[med]){
					return med;
				} else {
					right = med -1;
				}
			} else { // left < med, go right
				if(a[med]>a[med+1]){
					return med+1;
				}
				left = med + 1;
			}
		}
		
	}

}